/* This file contains the backtracking algorithm
*
*
*/

#include "sudoku.h"

/*
*	Performs recursive backtrack to find solution. Must provide a valid markup.
*/
bool backtrack(Grid g, Grid gSolved)
{
	bool solved = FALSE;
	int trialNum;
	cellCoord currCell;
	Grid trialGrid;
	
	if (isGridSolved(g)) 	// Recursive base case
	{		
		memcpy(gSolved, g, sizeof(cell) * 81);
		return TRUE;
	}
	
	// Save current grid
	trialGrid = newGrid();
	memcpy(trialGrid, g, sizeof(cell) * 81);
	
	// Get the cell with the least number of possibilities
	currCell = getLeastPossCell(trialGrid);
	
	// Guess solutions for the candidate cell
	for (trialNum = 0; trialNum < GRID_SIZE; trialNum++)
	{
		if((0x1 << trialNum) & gridIndex(trialGrid, currCell.x, currCell.y))	// This is a possible number
		{
			//printf("Trying cell: x:%d y:%d with :%d\n", currCell.x, currCell.y, trialNum + 1); debug
			// Set the number
			setCell(trialNum + 1, &gridIndex(trialGrid, currCell.x, currCell.y));
			
			// Markup cells resulting from the change
			markup(trialGrid);
			
			// Recursively call backtrack on next cell
			solved = backtrack(trialGrid, gSolved);			
			
			if(solved == TRUE) return TRUE;
			
			// If we reach here, we the trial number didn't work, so undo it
			memcpy(trialGrid, g, sizeof(cell) * 81);
		}
	}
	
	// No more cells to check. Dead end. 
	//printf("Deadend\n"); debug
	delGrid(trialGrid);
	return FALSE;
}

